package hot;

public class siwu {
//    class Solution {
//        public int jump(int[] nums) {
//            int n=nums.length;
//            int[] f=new int[n];
//            for(int i=0;i<n;i++){
//                f[i]=Integer.MAX_VALUE;
//            }
//            f[0]=0;
//            for(int i=1;i<n;i++){
//                for(int j=0;j<=i-1;j++){
//                    if(nums[j]+j>=i){
//                        // if(f[i]>f[j]+1){
//                        //     f[i]=f[j]+1;
//                        // }
//                        f[i]=Math.min(f[i],f[j]+1);
//                    }
//                }
//            }
//
//
//            return f[n-1];
//
//
//        }
//    }

    /**
     * 贪心策略
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int n=nums.length;
        int left=0;
        int right=0;
        int count=0;
        int maxright=0;
        while(left<=right){
            if(maxright>=n-1){
                return count;
            }
            for(int i=left;i<=right;i++){
                maxright=Math.max(maxright,nums[i]+i);
            }
            left=right+1;
            right=maxright;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums={2,3,1,1,4};
        int jump = jump(nums);
        System.out.println(jump);
    }
}
